/*
 * @lc app=leetcode.cn id=838 lang=cpp
 *
 * [838] 推多米诺
 */

// @lc code=start
class Solution
{
public:
    string pushDominoes(string dominoes)
    {
        int n = dominoes.size();
        queue<int> q;
        vector<int> time(n, -1);
        vector<string> force(n);
        for (int i = 0; i < n; i++)
        {
            if (dominoes[i] == '.')
            {
                continue;
            }
            q.emplace(i);
            time[i] = 0;
            force[i] = dominoes[i];
        }

        string ans(n, '.');
        while (!q.empty())
        {
            int idx = q.front();
            q.pop();
            if (force[idx].size() == 1)
            {
                char f = force[idx][0];
                ans[idx] = f;
                int nIdx = f == 'L' ? idx - 1 : idx + 1;
                if (nIdx >= 0 && nIdx < n)
                {
                    int t = time[idx];
                    if (time[nIdx] == -1)
                    {
                        q.emplace(nIdx);
                        time[nIdx] = t + 1;
                        force[nIdx].push_back(f);
                    }
                    else if (time[nIdx] == t + 1)
                    {
                        force[nIdx].push_back(f);
                    }
                }
            }
        }
        return ans;
    }
};
// @lc code=end
